// https://leetcode.cn/problems/advantage-shuffle/description/

// 算法思路总结：
// 1. 使用田忌赛马贪心策略优化优势计数
// 2. 排序nums1，对nums2索引按值排序保持原顺序映射
// 3. 用nums1最小元素对抗nums2最大元素，优势元素对抗对应位置
// 4. 时间复杂度：O(nlogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) 
    {
        int m = nums1.size();

        vector<int> index(m);
        for (int i = 0 ; i < m ; i++)
            index[i] = i;

        sort(nums1.begin(), nums1.end());
        sort(index.begin(), index.end(), [&nums2](const int& r1, const int& r2){
            return nums2[r1] < nums2[r2];
        });

        int l = 0, r = m - 1;
        vector<int> ret(m);
        for (int i = 0 ; i < m ; i++)
        {
            if (nums1[i] > nums2[index[l]])
            {
                ret[index[l]] = nums1[i];
                l++;
            }
            else
            {
                ret[index[r]] = nums1[i];
                r--;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> v11 = {2,7,11,15}, v12 = {1,10,4,11};
    vector<int> v21 = {12,24,8,32}, v22 = {13,25,32,11};
    Solution sol;

    auto r1 = sol.advantageCount(v11, v12);
    auto r2 = sol.advantageCount(v21, v22);

    for (const int& num : r1)
        cout << num << " ";
    cout << endl;

    for (const int& num : r2)
        cout << num << " ";
    cout << endl;

    return 0;
}

